package org.deng.learn.basic.algorithm;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author Deng
 * @date 2022/7/30 10:15
 * @desc 逆波兰表达式
 */
public class ReversePolishNotation {


    private static boolean isOperator(Character s) {
        return s.equals('+') || s.equals('-') || s.equals('*') || s.equals('/') || s.equals('(') || s.equals(')');
    }


    /**
     * 优先级是否小于或等于
     *
     * @param c
     * @param peek
     * @return
     */
    private static boolean lessOrEqualStackTop(char c, char peek) {
        if (peek == '(') {
            return false;
        }
        if (c == '+' || c == '-') {
            return true;
        }
        return peek == '*' || peek == '/';
    }

    /**
     * 创建逆波兰表达式（后缀表达式）
     *
     * @param expression
     * @return
     */
    private static List<String> createRPN(String expression) {
        List<String> sb = new ArrayList<>();
//        if(isOperator(expression.charAt(0)) || isOperator(expression.charAt(expression.length()-1))){
//            return sb;
//        }
        Stack<Character> stack = new Stack<>();

        expression = expression.trim().replace(" ", "");
        int start = 0;
        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);
            //是数字 并且前面一个不是数字
            if(!isOperator(c)&& (i==0 || isOperator(expression.charAt(i-1)))){
                start = i;
            }
            //是符号
            if (isOperator(c)) {
                //输出符号前面的数字
                if(!isOperator(expression.charAt(start))){
                    String num = expression.substring(start, i);
                    sb.add(num);
                    start = i;
                }


                if (stack.isEmpty() || c == '(') {
                    stack.push(c); //符号入栈
                } else {
                    if (c == ')') { //右括号
                        while (true) {
                            char top = stack.pop(); //出栈 直到左括号
                            if (top != '(') {
                                sb.add(top+""); //输出符号
                            } else {
                                break;
                            }
                        }

                    } else { // 运算符号
                        // 优先级不高于栈顶符号（乘除优先加减）则栈元素依次出栈并输出
                        while (!stack.isEmpty()) {
                            if (lessOrEqualStackTop(c, stack.peek())) {
                                sb.add(stack.pop()+"");
                            } else {
                                break;
                            }
                        }
                        //然后再入栈
                        stack.push(c);
                    }
                }

            }

        }

        //输出最后的数字
        String s = expression.substring(start);
        if(!s.startsWith(")")){
            sb.add(s);

        }

        //栈中元素出栈
        while (!stack.isEmpty()){
            sb.add(stack.pop()+"");
        }

        return sb;
    }

    /**
     * 逆波兰表达式求值
     * @param rpn
     * @return
     */
    private static int evalRPN(List<String> rpn){
        Stack<Integer> stack = new Stack<>();
        for (String s : rpn) {
            if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")){
                int b = stack.pop();
                int a = stack.pop();
                if(s.equals("+")){
                    stack.push(a + b);
                }else if(s.equals("-")){
                    stack.push(a - b);
                }else if(s.equals("*")){
                    stack.push(a * b);
                }else {
                    stack.push(a / b);
                }
               // System.out.println(stack.toString());
            }else {
                stack.push(Integer.parseInt(s));
               // System.out.println(stack.toString());
            }
        }
        return stack.pop();
    }

    public static void main(String[] args) {
        String expression = "(((6 + 3) * ((5 + 5) - 2) * 2 + (3+2)) + 8) * 2";

        List<String> rpn = createRPN(expression);
        System.out.println(rpn);


        int result = evalRPN(rpn);
        System.out.println(result);
    }


}
